﻿/*Thông tin*********************************************************************
 *Tên tập tin	: Graph_Vertex_cover.h
 *Mô tả			: Thư viên các thuật toán tìm phủ đỉnh
 *Ngày tạo		: 16/10/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các thuật toán tìm Phủ đỉnh*/
class COVER : public GRAPH	{
private:
	// Kích thước phủ đỉnh
	uint16_t k;

public:
	// Phương thức khởi tạo
	COVER();

	// Khởi tạo thuật toán tìm lớp phủ đỉnh kích thước không lớn hơn k
	void Initiate_Cover();
	// Tìm lớp phủ đỉnh kích thước không lớn hơn k-1
	bool Vertex_cover(vector <vector <uint16_t> > temp, uint16_t not, uint16_t ver);
	// Thuật toán tìm lớp phủ đỉnh kích thước không lớn hơn k
	void Find_vertex_cover();

	// In kết quả tìm kiếm lớp phủ đỉnh
	void Print_result_to_out(string input_file);
	//Phân nhóm các đỉnh để in
	void Select_vertices_group(fstream &f);
	// In lớp phủ đỉnh
	void Print_result_to_dot(string input_file);
};/*Kết thúc khai báo lớp COVER*/

/*Phương thức hởi tạo*/
COVER :: COVER()	{
	neighbors.clear();
	k = 0;
}/*Kết thúc phương thức COVER*/

/*Khởi tạo thuật toán tìm lớp phủ đỉnh kích thước không lớn hơn k*/
void COVER :: Initiate_Cover()	{
//	srand(uint16_t(time(0)));
//	k = uint16_t( rand() ) % Get_vertices() + 1;
	k = Get_vertices() / 2;

	Build_neighbors();

	cout << "Kich thuoc lop phu dinh can tim la " << k << ".\n"
		 << "Thuc hien thuat toan tim kiem lop phu dinh..........";
	start_time = clock();
}/*Kết thúc hàm Initiate_Cover*/

/*Tìm lớp phủ đỉnh kích thước không lớn hơn k-1*/
bool COVER :: Vertex_cover(vector <vector <uint16_t> > temp, uint16_t not, uint16_t ver)	{
	// Loại đỉnh not và các đỉnh lân cận của nó
	if (not != UINT16_MAX)	{
		temp[not].clear();

		for (uint16_t i=0; i<temp.size(); i++)
			for (uint16_t j=0; j<temp[i].size(); j++)
				if (temp[i][j] == not)
					temp[i].erase(temp[i].begin() + j);
	}

	// Đếm số cạnh hiện tại
	uint16_t counter = 0;
	
	for (uint16_t i=0; i<temp.size(); i++)
		counter = counter + temp[i].size();

	// Bắt đầu thuật toán
	if (!counter)
		return true;
	else if (counter > k * ver)
		return false;
	else	{
		uint16_t i;

		for (i=0; i!=temp.size(); ++i)
			// Kiểm tra xem từ i có cạnh nào không
			for (uint16_t k = 0; k!=temp[i].size(); ++k)	{
				if (Vertex_cover(temp, i, ver-1))	{
					result.push_back(i);
					return true;
				}
				else	{
					uint16_t j;

					for (j=0; j!=temp[i].size(); ++j)
						if (Vertex_cover(temp, temp[i][j], ver-1))	{
							result.push_back(temp[i][j]);
								return true;
						}
			
					if (j == temp[i].size())
						return false;
				}

				break;
			}

		if (i == temp.size())
			return false;
	}
}/*Kết thúc hàm Vertex_cover*/

/*Thuật toán tìm lớp phủ đỉnh kích thước không lớn hơn k*/
void COVER :: Find_vertex_cover()	{
	bool ok = Vertex_cover(neighbors, UINT16_MAX, Get_vertices());

	Print_runtime();
}/*Kết thúc hàm Find_Vertex_cover*/

/*In kết quả ra file*/
void COVER :: Print_result_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Cover", ".out");

	// Bắt đầu lưu kết quả
	if (result.size() > k || result.size() == 0)	{
			f << "Do thi vua nhap khong co phu dinh kich thuoc khong lon hon " << k << ".\n";
			cout << "Xong.\n";
			f.close();
			return;
		}

	f << "Cac dinh trong Phu dinh kich thuoc khong lon hon " << k << " la: \n";

	for (uint16_t i=0; i!=result.size(); ++i)
		f << result[i] + 1 << " ";

	f << "\n";
	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_result_to_out*/

/*In tập phủ đỉnh ra file .dot*/
void COVER :: Print_result_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Cover", ".dot");

	// Bắt đầu lưu
	f << "digraph " << input_header << "_Cover" << " {\n";

	if (result.size() > k || result.size() == 0)	{
		f << "label = \"\\n\\nDo thi nhap tu file " << input_file 
		  << " khong co phu dinh kich thuoc khong lon hon " << k << ".\"\n}";
	}
	else	{
		// Các đỉnh nằm trong tập kết quả được tô màu đỏ
		f << "node [style = filled, color = red]";
		for (uint16_t i=0; i!=result.size(); ++i)
			f << " " << result[i]+1;
		f << "\n";

		// Các đỉnh còn lại tô màu xanh
		f << "node [style = filled, color = green]";
		vector <uint16_t> b(Get_vertices());

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			b[i] = i+1;

		for (uint16_t i=0; i!=result.size(); ++i)
			b[result[i]] = UINT16_MAX;

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			if (b[i] != UINT16_MAX)
				f << " " << b[i];
		f << "\n";

		for (uint16_t i=0; i<Get_vertices(); ++i)
			for (uint16_t j=0; j<Get_vertices(); ++j)
				if (Get_length(i, j) != UINT16_MAX)
					f << i+1 << " -> " << j+1 << " [label = \"" << Get_length(i, j) << "\"]\n";

		f << "label = \"\\n\\nPhu dinh kich thuoc khong lon hon " << k 
		  << "\\ncua do thi voi du lieu tu file " << input_file << "\"\n}";
	}
	
	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_result_to_dot*********************************************/
